//------------------------------------------------------------------
// Purpose:     This program demonstrates bucket_sort.
// Author:      John Gauch
//------------------------------------------------------------------
#include <iostream>
#include <fstream>
#include <cstdlib> 
using namespace std;

//---------------------------------------------------------------------
// Prompt user for program parameters. 
//---------------------------------------------------------------------
void get_parameters(int &num_values, float &min, float &max, int &num_buckets)
{
   // Prompt user for program parameters
   string str;
   cout << "Enter number of data values: ";
   cin >> str;
   num_values = stoi(str);

   cout << "Enter minimum data value: ";
   cin >> str;
   min = stof(str);

   cout << "Enter maximum data value: ";
   cin >> str;
   max = stof(str);

   cout << "Enter number of buckets: ";
   cin >> str;
   num_buckets = stoi(str);
}

//------------------------------------------------------------------
// Initialize data array with random values between min and max.
//------------------------------------------------------------------
void random_data(float data[], int num_values, float min, float max)
{
   // Put random numbers into data array
   for (int index = 0; index < num_values; index++)
      data[index] = min + rand() * (max - min) / RAND_MAX;
}

//------------------------------------------------------------------
// Check to see if data is correctly sorted
//------------------------------------------------------------------
bool check_sorted(float data[], int num_values)
{
   // Put random numbers into data array
   bool sorted = true;
   for (int index = 1; index < num_values; index++)
      if (data[index-1] > data[index])
         sorted = false;
   return sorted;
}

//------------------------------------------------------------------
// Write data array to output file.
//------------------------------------------------------------------
void write_data(string name, float data[], int count)
{
   // Open output file
   ofstream dout;
   dout.open(name.c_str());
   if (dout.fail())
      cout << "Error: could not open output file\n";

   // Write the data
   dout << count;
   for (int i = 0; i < count; i++)
   {
      if (i % 20 == 0)
	 dout << endl;
      dout << data[i] << " ";
   }

   // Close the file
   dout << endl;
   dout.close();
}

//----------------------------------------------------------------
// Bucket_sort algorithm.
//----------------------------------------------------------------
void bucket_sort(float data[], int num_values, float min, float max,
		 int num_buckets)
{
   // Count number of data values in each bucket
   int * count = new int[num_buckets];
   for (int i = 0; i < num_buckets; i++)
      count[i] = 0;
   float bucket_range = (max - min) / num_buckets;
   for (int index = 0; index < num_values; index++)
   {
       int bucket = (data[index] - min) / bucket_range;
       if ((bucket >= 0) && (bucket < num_buckets))
          count[bucket]++;
       else
          cout << "Error " << data[index] << endl;
   }
   
   // Calculate start index for each bucket
   int * start = new int[num_buckets];
   for (int i = 0; i < num_buckets; i++)
      start[i] = 0;
   for (int i = 1; i < num_buckets; i++)
      start[i] = start[i-1] + count[i-1];

   // Copy data into appropriate bucket
   float * copy = new float[num_values];
   for (int index = 0; index < num_values; index++)
      copy[index] = 0;
   for (int index = 0; index < num_values; index++)
   {
       // Find appropriate bucket
       int bucket = (data[index] - min) / bucket_range;
       if ((bucket >= 0) && (bucket < num_buckets))
       {
          // Make room for data value
          int pos = start[bucket]++;
          while ((pos > 0) && (copy[pos - 1] > data[index]))
          {
             copy[pos] = copy[pos-1];
             pos--;
          }
             
          // Copy data value
          copy[pos] = data[index];
       }
       else
          cout << "Error " << data[index] << endl;
   }
   
   // Copy data back to input array
   for (int index = 0; index < num_values; index++)
      data[index] = copy[index];
      
   // Release memory
   delete []count;
   delete []start;
   delete []copy;
}

//---------------------------------------------------------------------
// main program to test sorting functions
//---------------------------------------------------------------------
int main()
{
   // Get program parameters
   int num_values, num_buckets;
   float min, max;
   get_parameters(num_values, min, max, num_buckets);

   // Generate random input data
   float * data = new float[num_values];
   random_data(data, num_values, min, max);

   // Sort data using bucket sort
   write_data("data.unsorted", data, num_values);
   bucket_sort(data, num_values, min, max, num_buckets);
   write_data("data.sorted", data, num_values);

   // Check data is sorted
   if (!check_sorted(data, num_values))
      cout << "Error sorting data" << endl;
   delete []data;
}